import sortedcontainers


class Solution(object):
    def numsGame(self, nums):
        base = 10 ** 9 + 7
        st = sortedcontainers.SortedList()
        ans = []
        n = len(nums)
        left_sum = 0
        right_sum = 0
        for i in range(n):
            now_diff = nums[i] - i
            index = st.bisect_right(now_diff)
            st.add(now_diff)
            if i % 2 == 1:
                if index < (i + 1) // 2:
                    right_sum += st[(i + 1) // 2]
                    left_sum += now_diff - st[(i - 1) // 2]
                else:
                    right_sum += now_diff
                ans.append((right_sum - st[(i - 1) // 2] - left_sum) % base)
            else:
                if i == 0:
                    ans.append(0)
                else:
                    if index >= i // 2:
                        right_sum += now_diff - st[i // 2]
                        left_sum += st[i // 2 - 1]
                    else:
                        left_sum += now_diff
                    ans.append((right_sum - left_sum) % base)
        return ans


data = Solution()
nums = [3, 4, 5, 1, 6, 7]
print(data.numsGame(nums))
nums = [1, 2, 3, 4, 5]
print(data.numsGame(nums))
nums = [1, 1, 1, 2, 3, 4]
print(data.numsGame(nums))
nums = [0, 100, 200]
print(data.numsGame(nums))
